package com.lun.swordtowardoffer2.c04;

import com.lun.util.SinglyLinkedList.ListNode;

public class GetIntersectionNode {

	//方法3：计算两链长度
	public ListNode getIntersectionNode(ListNode head1, ListNode head2) {
		int count1 = countList(head1);
		int count2 = countList(head2);
		
		if(count1 < count2) {//使head1总是较长那条链
			ListNode temp = head1;
			head1 = head2;
			head2 = temp;
		}
		
		int diff = count1 - count2;
		while(diff-- > 0)
			head1 = head1.next;
		
		while(head1 != head2) {
			head1 = head1.next;
			head2 = head2.next;
		}
		
		return head1;
	}
	
	private int countList(ListNode head) {
		if(head == null) return 0;
		
		int count = 0;
		
		while(head != null) {
			count++;
			head = head.next;
		}
		
		return count;
	}
	
}
